//这里是图的第一个项目
//第一个任务是构建 WordNet 有向图：每个顶点v 都是一个整数，表示一个同义词集，
//每个有向边v→w 表示w是v的上位词。WordNet 有向图是一个有根 DAG：它是无环的，有一个顶点（根）是其他每个顶点的祖先。
//但是，它不一定是一棵树，因为一个同义词集可以有多个上位词
//用来创建 WordNet 有向图的两个数据文件。这些文件采用逗号分隔值(CSV) 格式：每行包含一系列字段，以逗号分隔。
//1.同义词集列表。 文件synsets.txt 包含 WordNet 中的所有名词同义词集，每行一个。文件的第i行（从 0 开始计数）包含同义词集i的信息。
//第一个字段是同义词集 id，始终为整数i；第二个字段是同义词集（或synset）；第三个字段是其词典定义（或gloss），与此作业无关。
//例如，第 36 行表示同义词集 { AND_circuit, AND_gate} 的 ID 号为 36，其注释为 a circuit in a computer that fires only when all of its inputs fire。
//构成同义词集的各个名词以空格分隔。如果名词包含多个单词，则下划线字符连接单词（而不是空格字符）
//2.上位词列表。 文件hypernyms.txt 包含上位词关系。文件的第i行（从 0 开始计数）包含同义词集i的上位词。
//第一个字段是同义词集 id，它始终是整数i；后续字段是同义词集的上位词的 id 编号。
//例如，第 36 行表示同义词集 36 ( AND_circuit AND_Gate) 有 42338 ( gate logic_gate) 作为其唯一的上位词。
//第 34 行表示同义词集 34 ( AIDS acquired_immune_deficiency_syndrome) 有两个上位词：47569 ( immunodeficiency) 和 48084 ( infectious_disease)。

import java.util.ArrayList;
import java.util.HashSet;

import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinearProbingHashST;
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.SequentialSearchST;
import edu.princeton.cs.algs4.Stack;

//最后记得把DEBUG之间的部分都删了
public class WordNet {
    // constructor takes the name of the two input files
    // 用两个输入文件构造
    // 图结构主要用上位词列表
    // 查询id对应那些单词用同义词集列表 用符号表，要求检测时间的话，那么就用哈希表。
    // 用哈希的话，存id，一个id对应一个两个三个单词的有点麻烦了，那就再加个表
    // 也就是一个用id检索单词的表，一个哈希检索id的表，一个有向图
    // 也就是三个数据结构
    // 说实话，前面两个也许可以用B树，但是我还不会，后面学到了再说
    // 注意到，一个单词也是对应着多个id的，这个点没想到，浪费了好长时间
    private Bag<String>[] idToWord;
    private LinearProbingHashST<String, ArrayList<Integer>> wordToId;
    private Digraph ancester;

    public WordNet(String synsets, String hypernyms) {
        // 初始化三个容器
        idToWord = (Bag<String>[]) new Bag[82192];
        wordToId = new LinearProbingHashST<String, ArrayList<Integer>>();
        ancester = new Digraph(82192);
        // 读取输入
        In in = new In(synsets);
        while (!in.isEmpty()) {
            String line = in.readLine();
            int i = 0;
            int id = 0;
            String words = new String();
            for (String splitPart : line.split(",")) {
                if (i == 0) {
                    try {
                        id = Integer.parseInt(splitPart);
                    } catch (NumberFormatException e) {
                        id = 0;
                    }
                    i++;
                } else if (i == 1) {
                    words = splitPart;
                    i++;
                } else {

                }
            }
            idToWord[id] = new Bag<String>();
            for (String everyWord : words.split(" ")) {
                idToWord[id].add(everyWord);
                if (!wordToId.contains(everyWord)) {
                    ArrayList<Integer> newArrayList = new ArrayList<Integer>();
                    newArrayList.add(id);
                    wordToId.put(everyWord, newArrayList);
                } else {
                    wordToId.get(everyWord).add(id);
                }

            }
        }
        // 有向图初始化
        In digraphIn = new In(hypernyms);
        while (!digraphIn.isEmpty()) {
            String line = digraphIn.readLine();
            int start = 0;
            int i = 0;
            int end = 0;
            for (String splitPart : line.split(",")) {
                if (i == 0) {
                    try {
                        start = Integer.parseInt(splitPart);
                    } catch (NumberFormatException e) {
                        start = 0;
                    }
                    i++;
                } else {
                    try {
                        end = Integer.parseInt(splitPart);
                        ancester.addEdge(start, end);
                    } catch (NumberFormatException e) {
                        end = 0;
                    }

                }
            }

        }
    }

    // returns all WordNet nouns
    // 返回所有WordNet中的名词，就是遍历点吧应该
    public Iterable<String> nouns() {
        ArrayList<String> a = new ArrayList<String>();
        for (Bag<String> bag : idToWord) {
            for (String word : bag) {
                a.add(word);
            }
        }
        return a;
    }

    // is the word a WordNet noun?
    // 判断一个单词是不是在图中
    public boolean isNoun(String word) {
        return wordToId.contains(word);
    }

    // distance between nounA and nounB (defined below)
    // distance(x, y) = length of shortest ancestral path of subsets A and B
    // SAP那个文件里解释了什么是最短共同祖先，这里只说一下思路
    // 就是两个点同时进行广度优先遍历，什么时候出现重复点了，那个点就是最短共同祖先。
    // 同时进行，同步进行，用distanceTo来确认走到哪里了。
    // 每次广度优先走一步，停一下检测是否已经找到最短祖先
    // 也就是分别用两个队列进行广度优先，再用一个list，每次走完一步添加一边的queue全部元素，再一个个地添加另一个queue的元素并检验是否存在相同元素
    // 考虑到后面得两个子集找最短路径，所以还是得优化一下
    // 后面outcast那个只需要两个参数就ok，一对一对地去计算。
    // 子集找也这么找得了
    // 一对一对地调用呗
    // 哦，不行。 那就用数组和循环，所以有点一起同步进行，然后进行检测，直到有一个最短的被检测出来
    // 那个到时候再用新的辅助函数，这个文件和outcast那个用这个两个参数的就够用了。
    // 考虑环的影响，必须考虑到再找到第一个ancestor之后，还允许多走最多多少步去寻找一个最短的ancestor
    // 也就是说，为了那个环的可能，你需要付出多少？
    // 允许最多步数<distance
    private class BFS_all {
        int distance;
        int ancestor;
        String edge;
    }

    private BFS_all BFS(Digraph g, int a, int b) {
        // ArrayList<Integer> marked = new ArrayList<Integer>(); 用于判断每步结束是否出现重复元素
        // 出现错误，没考虑到同一边的广度优先访问到同一个点
        HashSet<Integer> markedA = new HashSet<Integer>();
        HashSet<Integer> markedB = new HashSet<Integer>();
        LinearProbingHashST<Integer, Integer> distanceTo_A = new LinearProbingHashST<Integer, Integer>(); // 用于判断走了多远
        LinearProbingHashST<Integer, Integer> distanceTo_B = new LinearProbingHashST<Integer, Integer>();
        SequentialSearchST<Integer, Integer> edgeTo_A = new SequentialSearchST<Integer, Integer>(); // 用于返回路径
        SequentialSearchST<Integer, Integer> edgeTo_B = new SequentialSearchST<Integer, Integer>(); // 用于返回路径
        Queue<Integer> points_A = new Queue<Integer>();
        Queue<Integer> points_B = new Queue<Integer>();
        int ancestor_Id = -1; // 祖先的id
        points_A.enqueue(a);
        points_B.enqueue(b);
        markedA.add(a);
        markedB.add(b);
        if (markedB.contains(a) && ancestor_Id == -1) // 这里是找到了
        {
            ancestor_Id = a;
        }
        distanceTo_A.put(a, 0);
        distanceTo_B.put(b, 0);
        int A_loop = 0;
        int B_loop = 0;
        int i = 0;// 用i标注目前进行到第几步了
        // 这里开始是总循环，结束条件是到最后也没找到最短祖先（条件是两个队列都空了）或者找到了最短祖先。
        while (!(points_A.isEmpty() && points_B.isEmpty())
                && (ancestor_Id == -1 || i + 1 < distanceTo_A.get(ancestor_Id) + distanceTo_B.get(ancestor_Id))) {
            i++;
            // A走一步
            if (!points_A.isEmpty()) {
                for (A_loop = points_A.peek();; A_loop = points_A.peek()) {
                    if (distanceTo_A.get(A_loop) >= i) {
                        break;
                    } else {
                        A_loop = points_A.dequeue();
                    }
                    for (int point : g.adj(A_loop)) {
                        if (!markedA.contains(point)) {
                            points_A.enqueue(point);
                            edgeTo_A.put(point, A_loop);// point从A_loop那里来
                            distanceTo_A.put(point, distanceTo_A.get(A_loop) + 1);// pdistanceTo_A.get(ancestor_Id) +
                                                                                  // distanceTo_B.get(ancestor_Id)oint的距离是A_loop+1
                            markedA.add(point); // 添加以之后判断是否有重复元素
                            if (markedB.contains(point)
                                    && (ancestor_Id == -1 || distanceTo_A.get(ancestor_Id) + distanceTo_B
                                            .get(ancestor_Id) > distanceTo_A.get(point) + distanceTo_B.get(point))) // 这里是找到了
                            {
                                ancestor_Id = point;
                            }
                        }

                    }
                    if (points_A.isEmpty()) {
                        break;
                    }
                }
            }
            // B走一步
            if (!points_B.isEmpty()) {
                for (B_loop = points_B.peek();; B_loop = points_B.peek()) {
                    if (distanceTo_B.get(B_loop) >= i) {
                        break;
                    } else {
                        B_loop = points_B.dequeue();
                    }
                    for (int point : g.adj(B_loop)) {
                        if (!markedB.contains(point)) {
                            points_B.enqueue(point);
                            edgeTo_B.put(point, B_loop);
                            distanceTo_B.put(point, distanceTo_B.get(B_loop) + 1);
                            markedB.add(point);
                            if (markedA.contains(point)
                                    && (ancestor_Id == -1 || distanceTo_A.get(ancestor_Id) + distanceTo_B
                                            .get(ancestor_Id) > distanceTo_A.get(point) + distanceTo_B.get(point))) {
                                ancestor_Id = point;
                            }
                        }
                    }
                    if (points_B.isEmpty()) {
                        break;
                    }
                }
            }
        }
        BFS_all val = new BFS_all();
        val.ancestor = ancestor_Id;
        if (ancestor_Id == -1) // 没找到
        {
            val.distance = -1;
            val.edge = "-1";
            return val;
        }
        val.distance = distanceTo_A.get(ancestor_Id) + distanceTo_B.get(ancestor_Id);
        String edge = new String();
        // 这里是从A到ancestor
        Stack<Integer> path = new Stack<Integer>();
        for (int point = ancestor_Id; point != a; point = edgeTo_A.get(point)) {
            if (point == ancestor_Id) {
                continue;
            }
            path.push(point);
        }
        path.push(a);
        for (Integer point : path) {
            edge = edge + point + " ";
        }
        // 这里是从ancestor到B
        ArrayList<Integer> path_b = new ArrayList<Integer>();
        for (int point = ancestor_Id, k = 0; point != b; point = edgeTo_B.get(point), k++) {
            path_b.add(k, point);
        }
        path_b.add(b);
        for (Integer point : path_b) {
            edge = edge + point + " ";
        }
        val.edge = edge;
        return val;
    }

    public int distance(String nounA, String nounB) {
        ArrayList<Integer> id_A = wordToId.get(nounA);
        ArrayList<Integer> id_B = wordToId.get(nounB);
        int length = -1;
        int lengthMin = -1;
        for (Integer idOfA : id_A) {
            for (Integer idOfB : id_B) {
                length = BFS(ancester, idOfA, idOfB).distance;
                if (lengthMin == -1 || lengthMin > length) {
                    lengthMin = length;
                }
            }
        }
        return lengthMin;
    }

    // a synset (second field of synsets.txt) that is the common ancestor of
    // nounA
    // and nounB
    // in a shortest ancestral path (defined below)
    public String sap(String nounA, String nounB) {
        ArrayList<Integer> id_A = wordToId.get(nounA);
        ArrayList<Integer> id_B = wordToId.get(nounB);
        BFS_all length = new BFS_all();
        length.distance = -1;
        BFS_all lengthMin = new BFS_all();
        lengthMin.distance = -1;
        for (Integer idOfA : id_A) {
            for (Integer idOfB : id_B) {
                length = BFS(ancester, idOfA, idOfB);
                if (lengthMin.distance == -1 || lengthMin.distance > length.distance) {
                    lengthMin = length;
                }
            }
        }
        String out = new String();
        for (String ancestor : idToWord[lengthMin.ancestor]) {
            out = out + ancestor + " ";
        }
        return out;
    }

    // do unit testing of this class
    public static void main(String[] args) {
        WordNet test = new WordNet("synsets100-subgraph.txt", "hypernyms100-subgraph.txt");
        System.out.println("Hello, World!");
        System.out.println(test.distance("freshener", "thing"));

    }
}
